#include <bits/stdc++.h>
using namespace std;
int const MAXN = 1e6+10;
int prime[MAXN],v[MAXN];    //表示 i 的最小质因数。如果i就是质数，那么v[i] = i
int m=0;//m表示现在筛出m个质数
const int MO = 1e9+7;
typedef long long ll ;
void primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)        //如果v[i]为0，说明 i 之前没有被筛到过，i 为质数
        {
            v[i] = i;
            prime[++m] = i;
        }
        for(int j = 1;j<=m;j++)    //遍历小于 i 的所有质数
        {
            //如果质数大于 i 的最小质因数或者乘起来大于n就跳出循环
            if(prime[j] > v[i] || prime[j] > n/i) break;
            v[i*prime[j]] = prime[j];    //标记 i*prime[j] 的最小质因数是prime[j]
        }
    }
}
//int pow_mod(int a,int b,int c){
//    int ans = 1;
//    int base = a%c;
//    while(b){
//        if(b & 1) ans = (ans*base)%c;
//        base = (base*base)%c;
//        b >>= 1;
//    }
//    return ans;
//}
ll pow_mod(ll a,ll b){
    ll ans = 1;
    while(b){
        ans = ans * a %MO;
        --b;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    primes(MAXN);
    int T; cin >> T;
    while(T--){
        int n, c;
        cin >> n >> c;
        int ans = 0;
        while(n!=1){
            ++ans;
            n /= v[n];
        }
        cout << pow_mod(c, ans) << "\n";
    }
    return 0;
}